Ch.16 Polynomials of Matrices

The addition case is simple. To prove the product, for some $\vec{v}\in V$ write $f(t)\circ g(t)(\vec{v})=f(t)(g(t)(\vec{v}))=(c_nt^n+\cdots+c_1t+c_0\text{id}_V)(g(t)(\vec{v}))\\=c_nt^n(g(t)(\vec{v}))+\cdots+c_1t(g(t)(\vec{v}))+c_0(g(t)(\vec{v}))$
From $g(x)$ and the fact that $t^i$ is a linear map,
$\begin{array}{rcl}c_it^i(g(t)(\vec{v}))&=&c_it^i(d_mt^m(\vec{v})+\cdots+d_1t(\vec{v})+d_0(\vec{v}))\\&=&c_id_m(t^{i+m}(\vec{v}))+c_id_1(t^{1+i}(\vec{v}))+c_id_0(t^{i}(\vec{v}))\\\end{array}$
This is simply $p_i(t)$, where $p_i(x)=c_id_mx^{i+m}+\cdots+c_id_1x^{i+1}+c_id_0x^i=c_ix^i(d_mx^m+\cdots+d_1x+d_0)=c_ix^ig(x)$
Thus, from above,
$f(t)\circ g(t)(\vec{v})=p_n(t)(\vec{v})+\cdots+p_1(t)(\vec{v})+p_0(t)(\vec{v})$
From the sum case, we obtain $f(t)\circ g(t)(\vec{v})=S(t)(\vec{v})$ where $S(x)$ is
$\begin{array}{rcl}f(t)\circ g(t)(\vec{v})&=&c_nx^ng(x)+\cdots+c_1xg(x)+c_0g(x)\\&=&(c_nx^n+\cdots+c_1x+c_0)g(x)\\&=&f(x)g(x)\\&=&p(x)\end{array}$
Hence, $f(t)\circ g(t)(\vec{v})=p(t)(\vec{v})$ for all $\vec{v}\in V$, proving the result.

If $\vec{v}\in\mathscr{R}(f(t))$, then we can find a $\vec{w}\in V$ such that $\vec{v}=f(t)(\vec{w})$. Hence, $g(t)(\vec{v})=g(t)(f(t)(\vec{w}))=f(t)(g(t)(\vec{w}))\in\mathscr{R}(f(t))$.
Similarly, if $\vec{v}\in\mathscr{N}(f(t))$, then $f(t)(g(t)(\vec{v}))=g(t)(f(t)(\vec{v}))=g(t)(\vec{0})=\vec{0}$.

We have $t^i(\vec{v})=\lambda^i\vec{v}$. Therefore, if $f(x)=c_nx^n+\cdots+c_1x+c_0$, then $f(t)(\vec{v})=c_nt^n(\vec{v})+\cdots+c_1t(\vec{v})+c_0=c_n\lambda^n(\vec{v})+\cdots+c_1\lambda(\vec{v})+c_0=f(\lambda)(\vec{v})$

It suffices to prove the matrix case.
Since the $\mathcal{M}_{2\times 2}$ vector space has dimension $n^2$, the $n^2+1$ member set $\{I, T, T^2,...,T^{n^2}\}$ must be linearly dependent. Thus, there exists scalars $c_0,...,c_{n^2}$ not all zero such that $c_{n^2}T^{n^2}+\cdots+c_1T+c_0I=0$. Hence, the polynomial $p(x)=c_{n^2}x^{n^2}+\cdots+c_1x+c_0$ is a non-zero polynomial for which $p(T)=0$.

Consider the matrix
$T=\begin{pmatrix}\cos{(\pi/3)}&-\sin{(\pi/3)}\\\sin{(\pi/3)}&\cos{(\pi/3)}\end{pmatrix}=\begin{pmatrix}1/2&-\sqrt{3}/2\\\sqrt{3}/2&1/2\end{pmatrix}$
The polynomial $p(x)=x^2-x+1=0$ satisfies $p(T)=0$

Let $\vec{v}$ be an eigenvector associated with eigenvalue $\lambda$ of $t$. Then $f(t)(\vec{v})=f(\lambda)(\vec{v})$. Since $f(t)=0$, we have $f(\lambda)(\vec{v})=0\implies f(\lambda)=0$ because $\vec{v}\ne0$ as eigenvectors are not $\vec{0}$

The zero matrix has minimal polynomial $m(x)=x$.
The identity matrix has minimal polynomial $m(x)=x-1$

First, we prove existence.
Since a polynomial exists that takes a map or polynomial to zero, we take the one with smallest degree. Divide by its leading coefficient to make it $1$. This satisfies the conditions, so a minimal polynomial exists.
Next, we prove uniqueness.
Suppose both $m(x)$ and $\hat{m}(x)$ are two polynomials that take the map or matrix to zero, are both minimal and equal degree, and have leading coefficient $1$. Consider the difference $m(x)-\hat{m}(x)$. If this is not zero, then it has a nonzero leading coefficient. Dividing by that coefficient gives a polynomial that takes a map or matrix to zero, has leading coefficient $1$, and is smaller degree than $m$ and $\hat{m}$. This contradicts the minimality of $m$ and $\hat{m}$, thus $m(x)-\hat{m}(x)=0$, making the two equal.

Let $m(x)$ be the minimal polynomial of the linear map $t:V\to V$. Since $m(t)=0$, all eigenvalues are roots of $m(x)$. It remains to show that every root of $m(x)$ is an eigenvalue of $t$. If $r$ is a root of $m(x)$, then we can write $m(x)=(x-r)p(x)$ for a polynomial $p(x)$ with smaller degree than $m(x)$. Since $m(x)$ is the minimal polynomial of $t$, $p(t)$ is not the zero map. Therefore, there is a vector $\vec{v}\in V$ such that $p(t)(\vec{v})\ne\vec{0}$. Using this, we have $m(t)(\vec{v})=(t-r\text{ id}_V)(p(x)(\vec{v}))$. Using $m(t)=0$ and distributing, $t(p(t)(\vec{v}))-rp(t)(\vec{v})=0\implies t(p(t)(\vec{v}))=rp(t)(\vec{v})$ which means $r$ is an eigenvalue of $t$ with eigenvector $p(t)(\vec{v})$

Let $m(x)$ be the minimal polynomial of $T$. Then according to the division theorem for polynomials, $f(x)=q(x)\cdot m(x)+r(x)$, with $r(x)$ having degree strictly less than $m(x)$. Since $T$ satisfies both $f$ and $m$, $m(T)=f(T)=0$, so $r(T)$ must also be the zero map. This would contradict the minimality of $m$ unless $r$ was the zero polynomial.

Let $C=T-xI$, the matrix whose determinant is the characteristic polynomial $c(x)=c_nx^n+\cdots+c_1x+c_0$. Since the product of a matrix and its adjoint is its determinant times the identity, we can write $c(x)\cdot I=\text{adj}(C)C=\text{adj}(C)(T-xI)=\text{adj}(C)T-\text{adj}(C)\cdot x$
The left side is $c_nIx^n+\cdots+c_1Ix+c_0I$. For the right, $\text{adj}(C)$ is a matrix of polynomials, therefore it can be expressed as a polynomial with matrix coefficients: $\text{adj}(C)=C_{n-1}x^{n-1}+\cdots+C_1x+C_0$, with each $C_i$ being a matrix of scalars, making the right side $[(C_{n-1}T)x^{n-1}+\cdots+(C_1T)x+C_0T]-[C_{n-1}x^n+\cdots+C_1x^2+C_0x]$
Equate the coefficients on each side:
$c_nI=-C_{n-1}\\c_{n-1}I=C_{n-1}T-C_{n-2}\\\vdots\\c_1I=C_1T-C_0\\c_0I=C_0T$
Multilply the first equation by $T^n$, the second equation by $T^{n-1}$, etc.
$c_nT^n=-C_{n-1}T^n\\c_{n-1}T^{n-1}=C_{n-1}T^n-C_{n-2}T^{n-1}\\\vdots\\c_1T=C_1T^2-C_0T\\c_0I=C_0T$
Adding all the equations, many cancel out, giving
$c_nT^n+c_{n-1}T^{n-1}+\cdots+c_0I=c(T)=0$

Find the minimal polynomial of the following matrix
$T=\begin{pmatrix}2&0&0&1\\1&2&0&2\\0&0&2&-1\\0&0&0&1\end{pmatrix}$

The characteristic polynomial is easily computed as $c(x)=(x-1)(x-2)^3$. Thus, by the Cayley-Hamilton Theorem, the minimal polynomial is either $(x-1)(x-2)$, $(x-1)(x-2)^2$, or $(x-1)(x-2)^3$. We compute to check:
$(T-I)(T-2I)=\begin{pmatrix}1&0&0&1\\1&1&0&2\\0&0&1&-1\\0&0&0&0\end{pmatrix}\begin{pmatrix}0&0&0&1\\1&0&0&2\\0&0&0&-1\\0&0&0&-1\end{pmatrix}=\begin{pmatrix}0&0&0&0\\1&0&0&1\\0&0&0&0\\0&0&0&0\end{pmatrix}$
$(T-I)(T-2I)^2=\begin{pmatrix}0&0&0&0\\1&0&0&1\\0&0&0&0\\0&0&0&0\end{pmatrix}\begin{pmatrix}0&0&0&1\\1&0&0&2\\0&0&0&-1\\0&0&0&-1\end{pmatrix}=\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}$
So $m(x)=(x-1)(x-2)^2$

Call $\lambda_1,...,\lambda_l$ the distinct roots of the characteristic polynomial of the linear map $t$ on the $n$-dimensional vector space $V$. Note that $\lambda_1,...,\lambda_l$ are the distinct roots of the minimal polynomial $m(x)$ of $t$.
Suppose $t$ is diagonalizable. Then there exists a basis $B=\langle\vec{v}_1,...,\vec{v}_n\rangle$ with each $\vec{v}_i$ an eigenvector of $t$. Consider the polynomial $p(x)=(x-\lambda_1)\cdots(x-\lambda_l)$. We claim $p(t)=0$. It suffices to check $p(t)(\vec{v}_i)=0$ for all $\vec{v}_i$. We know $p(t)(\vec{v}_i)=p(\lambda_i)(\vec{v}_i)$, but $p(\lambda_i)=(\lambda_i-\lambda_1)\cdots(\lambda_i-\lambda_l)=0$ since $\lambda_i\in\{\lambda_1,...,\lambda_l\}$, thus $p(t)(\vec{v}_i)=0$. Thus, the minimal polynomial $m(x)$ must divide $p(x)$. Therefore, $m(x)$ also has simple roots, and is in fact equal to $p(x)$ since $\lambda_1,...,\lambda_l$ are the distinct roots of $m(x)$. Thus, $t$ is diagonalizable $\implies m(x)$ has simple roots.
To prove the converse, we perform induction on the number of eigenvalues $l$, which is the dimension of $m(x)$.
If $T$ has only one eigenvalue, then $m(x)=x-\lambda_1\implies m(t)=t-\lambda_1\text{ id}_V=0\implies t=\lambda_1\text{ id}$ meaning it is diagonal.
Let $m(x)=(x-\lambda_1)\cdots(x-\lambda_l)$. Let $p(x)=(x-\lambda_2)\cdots(x-\lambda_l)$ so that $m(x)=(x-\lambda_1)p(x)$. Suppose the statement is true if the minimal polynomial has degree less than $l$. Call $\hat{V}=\mathscr{N}(p(t))$. Since $t(\hat{V})\subseteq\hat{V}$, we can define a linear map $\hat{t}:\hat{V}\to\hat{V}$ by $\hat{t}(\vec{v})=t(\vec{v})$ for $\vec{v}\in\hat{V}$. Therefore, if $\hat{m}(x)$ is the minimal polynomial for $\hat{t}$, $\hat{m}(x)$ divides $p(x)$, making the roots simple. Since there are at most $l-1$ roots thats are all simple, we can find a basis $\langle\vec{w}_1,...,\vec{w}_{k}\rangle$ of $\hat{V}$ consisting of eigenvectors $\vec{w}_j$ of $\hat{t}$ (hence of $t$) with associated eigenvalues $\mu_j\in\{\lambda_2,...,\lambda_l\}$.
Since $\hat{V}=\mathscr{N}(p(t))$ has $k$ vectors in the basis, the nullity of $p(t)$ is $k$. Hence, $k+\text{rank}(p(t))=n$, the dimension of $V$.
Next, we show that $\mathscr{R}(p(t))\subseteq\mathscr{N}(t-\lambda_1\text{ id}_V)$. If $\vec{v}\in\mathscr{R}(p(t))$, we can find a $\vec{w}\in V$ such that $\vec{v}=p(t)(\vec{w})\implies(t-\lambda_1\text{id}_V)(\vec{v})=(t-\lambda_1\text{id}_V)(p(t)(\vec{w}))$, but since $(x-\lambda_1)p(x)=m(x)$, $(t-\lambda_1\text{id}_V)(\vec{v})=m(t)(\vec{w})=\vec{0}$, completing the proof.
If $m$ was the nullity of $(t-\lambda_1\text{ id}_V)$, we must have $m+k\ge\text{rank}(p(t))+k=n$. Pick a basis $\langle\vec{v}_1,...,\vec{v}_m\rangle$. Each $\vec{v}_i$ is an eigenvector of $t$ associated with eigenvalue $\lambda_1$.
We claim $\langle\vec{v}_1,...,\vec{v}_m,\vec{w}_1,...,\vec{w}_k\rangle$ is a basis of $V$. Since $m+k\ge n$, it suffices to show these vectors are linearly independent. Suppose we can find scalars $\alpha_1,...,\alpha_m,\beta_1,...,\beta_k$ such that
$\alpha_1\vec{v}_1+\cdots+\alpha_m\vec{v}_m+\beta_1\vec{w}_1+\cdots+\beta_k\vec{w}_k=0$
Applying the map $(t-\lambda_1\text{id}_V)$ to the above equation and considering that $(t-\lambda_1\text{ id}_V)(\vec{v}_i)=\vec{0}$ and $(t-\lambda_1\text{ id}_V)(\vec{w}_j)=(\mu_j-\lambda_1)\vec{w}_j$, we simplify to
$\beta_1(\mu_1-\lambda_1)\vec{w}_1+\cdots+\beta_k(\mu_k-\lambda_1)\vec{w}_k=\vec{0}$
Since $\langle\vec{w}_1,...,\vec{w}_k\rangle$ is a basis of $V$, this implies $\beta_j(\mu_j-\lambda_1)=0$ for all $j=1,...,k$. But $\mu_j-\lambda_1\ne0$ since $\mu_j\in\{\lambda_2,...,\lambda_l\}$ and all the $\lambda_i$'s are distinct. Therefore, all of the $\beta_j=0$, reducing the linear dependence relation to
$\alpha_1\vec{v}_1+\cdots+\alpha_m\vec{v}_m=0$
Since $\langle\vec{v}_1,...,\vec{v}_m\rangle$ is a basis for $\mathscr{N}(t-\lambda_1\text{ id}_V)$, we conclude $\alpha_i=0$ for all $i=1,...,m$. Therefore, $\langle\vec{v}_1,...,\vec{v}_m,\vec{w}_1,...,\vec{w}_k$ is a basis of $V$ consisting of eigenvectors of $t$. Hence, $t$ is diagonalizable.

The derivative map $d/dx:\mathcal{P}_3\to\mathcal{P}_3$, we have
$a+bx+cx^2+dx^3\xmapsto{d/dx}b+2cx+3dx^2$
$a+bx+cx^2+dx^3\xmapsto{d^2/dx^2}2c+6dx$
$a+bx+cx^2+dx^3\xmapsto{d^3/dx^3}6d$
and any higher power maps to $0$.

If $\vec{w}\in\mathscr{R}(t^{j+1})$, so that $\vec{w}=t^{j+1}(\vec{v})$ for some $\vec{v}$, then $\vec{w}=t^j(t(\vec{v}))$, so $\vec{w}\in\mathscr{R}(t^j)$. So $\mathscr{R}(t^{j+1})\subseteq\mathscr{R}(t^j)$. If $\mathscr{R}(t^k)=\mathscr{R}(t^{k+1})$, then $\mathscr{R}(t^{k+1})=\mathscr{R}(t^{k+2})$ by induction, since we have the same map with the same domain and same range. Also, because $V$ is finite-dimensional and proper subsets must have dimension strictly less than its superset, it must eventually stop.
Finally, by rank-nullity theorem, the opposite is true of the nullspace.

For the derivative map $d/dx:\mathcal{P}_3\to\mathcal{P}_3$ from before, we have the following chain of range spaces:
$\mathcal{P}_3\supset\mathcal{P}_2\supset\mathcal{P}_1\supset\mathcal{P}_0\supset\{\vec{0}\}$
and the following chain of null spaces:
$\{\vec{0}\}\subset\mathcal{P}_0\subset\mathcal{P}_1\subset\mathcal{P}_2\subset\mathcal{P}_3$

Let the dimension of $V$ be $n$. Because $\mathscr{R}(t^n)=\mathscr{R}(t^{n+1})=t(\mathscr{R}(t^n))$, the map $t:\mathscr{R}_\infty(t)\to\mathscr{R}_\infty(t)$ is onto. Therefore, it is one-to-one.
Next, assume $\vec{v}\in\mathscr{R}_\infty(t)\cap\mathscr{N}_\infty(t)$. Since $\vec{v}$ is in the generalized null space, $t^n(\vec{v})=\vec{0}$. On the other hand, since $t$ is one-to-one and a composition of one-to-one functions is also one-to-one, $t^n$ is also one-to-one. Only $\vec{0}$ maps to $\vec{0}$ in a one-to-one linear map so $t^n(\vec{v})=\vec{0}$ implies $\vec{v}=\vec{0}$.

Let the dimension of $V$ be $n$. By rank-nullity, $k+l=n$, so $B=\langle\vec{v}_1,...,\vec{v}_k,\vec{w}_1,...,\vec{w}_l\rangle$ has $n$-vectors. To show $B$ is a basis of $V$, it suffices to show that this set is linearly independent. But this follows from the fact that $\mathscr{R}_\infty(t)\cap\mathscr{N}_\infty(t)=\{\vec{0}\}$